Consider, as a motivating example, a service provider that wishes to partner with other service providers in order to provide a richer set of services to its customers. If company A is providing Internet access service through its own network, then its customers are typically limited to accessing such an Internet service from company A's network. However, it might make sense from a business perspective for company A to partner with company B, which also provides Internet access via a network. The partnership may include an agreement whereby company B agrees to provide service to company A's customers, as long as company A provides appropriate reimbursement to company B (e.g., from company A's proceeds from appropriately billing the customers that used company B's network). Company A may agree to provide a similar service to company B's customers.
However, a number of problems arise when trying to implement such an arrangement. First, company A must get accurate accounting information, so that it can bill its customers appropriately. Second, company B must not be able to cheat by overstating usage of its network by company A's customers. Third, company A's customers should not be able to get any free access to company B's network. Therefore, the accounting mechanism should account for all customer usage.
Prior art solutions to these problems create significant additional costs. These additional costs are not only monetary, but may be considerable in terms of the amount of computation time, computer memory, and/or electrical power required by the devices owned by the various parties. These factors may be especially important when the customers are using mobile devices, which may have severe computational, memory and power constraints.
To the best of our knowledge, there is no prior art for methods, systems, or components for handling the situations discussed above with sufficient efficiency.
One naive solution is to use a micropayment scheme, in which a “bank generates “coins” for its customers, which they can spend to pay for services provided by various merchants. The user pre-pays for these coins, and the system is debit-based. If an Internet service is being accessed, for example, the user can include one coin with every packet of data it sends over the foreign service provider's (FSP's) network. The FSP is provided with a mechanism for validating these coins. After validating a coin, the FSP may transmit the corresponding packet. Ultimately, the FSP provides all of these coins to the home service provider (HSP) so that the FSP can be reimbursed. The electronic payment system is secure in the sense that only the HSP can create valid electronic coins that no other party can forge.
This naive solution has a number of drawbacks. First of all, the solution does not scale well for the HSP. The HSP must generate all of the electronic coins used by its customers and securely transport those coins to each end user. If, as in the above example, a coin is used for every packet that a customer transmit over an FSP, then the number of coins that the HSP must generate is proportional to the entire volume of traffic that its customers impose on the FSP. This volume may be very significant, and it may be impractical for a single centralized server of the HSP to generate sufficient coins.
Second, the HSP has to handle verifying each coin when it is returned. The two possible ways that the HSP might do this are to maintain a list of every coin it issued or perform the same verification step as the FSP. In either case, the computation is again proportional to the total number of coins used by its customers, and this computation may therefore be infeasible. In the first case, the amount of storage necessary to store a huge table of all possible coins might be prohibitively expensive. In the second case, though less storage-intensive, it is more CPU-intensive, as performing the verification step like the FSP is slower than a table lookup.